import java.util.Arrays;
import java.util.ArrayList;
/*
 *  This class holds a B-tree index
 *  An index may be a combination of numeric and varchar columns
 *  Each column can be sorted independently ASC or DESC
 *  And example of a INT ASC, INT ASC (5,6) B-tree could look like this:
 *  
 *	Root pointer
 *	1,8,	2,6,	
 *		1,2,	1,4,	1,6,	
 *			1,1,	1,1,	1,2,	
 *			1,2,	1,3,	1,4,	
 *			1,4,	1,5,	1,6,	
 *			1,6,	1,7,	1,7,	
 *		2,1,	2,5,	
 *			1,8,	1,9,	2,1,	
 *			2,1,	2,2,	2,2,	
 *			2,5,	2,5,	
 *		2,9,	2,9,	
 *			2,7,	2,7,	2,8,	2,8,	
 *			2,9,	2,9,	
 *			2,9,	2,9,	2,10,	2,10,	2,10,	
 *
 *  Each node should have a internal values count so that it fills only 1 page for less I/O ops
 *  This will of course depend on the number of columns and their size. 
 *  
 *  OBS OBS OBS Only working with INTs
 *  Must be fixed in the compareSets and equalSets functions
 *  
*/

public class db_index_engine {
	private db_index_node root;
	private int t = db_util.DB_INDEX_SIZE/2;
	private ArrayList<db_index_compare> oCompares;

	db_index_engine(ArrayList<db_index_compare> oComparesPointer){
		oCompares = oComparesPointer;
		db_index_node x = new db_index_node();
		x.leaf = true;
		x.nValCnt = 0;
		root = x;
	}
	
	public db_index_value search(db_bytes k) {
		k.seek(0);
		return searchno(root, k, 0);
	}

	public db_index_value searchno(db_index_node x, db_bytes k, int p) {
		// Finds the first node in a left to right deep search
		// This enables us to traverse the tree using getNextNode, in a left->right depth first mode
		db_index_value oRes = null;
		p++;
		//System.out.println("Start");
		for (int i = 0; i < x.nValCnt; i++) {


			if (!x.leaf) {

				// search right or left branch?
				if (compareSets(k, x.values[i].oBytes) || equalSets(k, x.values[i].oBytes)) {
					//System.out.println("searching left leaf");
					oRes = searchno(x.leaves[i], k, p);
				} else
					if (i == x.nValCnt-1) {
						//System.out.println("searching right leaf");
						oRes = searchno(x.leaves[i+1], k, p);
					}
				if (oRes != null) {
					//System.out.println("Found a result in leaf node");
					return oRes;
				}
			} 
			if (equalSets(k, x.values[i].oBytes) && !x.values[i].bDeleted)
				return x.values[i];
			//System.out.println("Didn't find result in myself, try next sister");
		} 

		return oRes;
	}

	public db_index_value next(db_index_value x, int iComparisonOperator) {


		if (iComparisonOperator == db_util.DB_COMPARE_EQ) {
			while (x.oNext != null && equalSets(x.oBytes, x.oNext.oBytes)) {
				if (!x.oNext.bDeleted)
					return x.oNext;
				x = x.oNext;
			}
			
			return null;
		} else {
			while (x.oNext != null) {
				if (!x.oNext.bDeleted)
					return x.oNext;
				x = x.oNext;
			}
		}
		
		return null;
	}

	private void split(db_index_node x, int i, db_index_node y) {

		db_index_node z = new db_index_node();
		z.leaf = y.leaf;
		z.nValCnt = t -1;
		for (int j = 0; j < t -1; j++) {
			z.values[j] = y.values[j+t];
		}
		if (!y.leaf) {
			for (int j = 0; j < t; j++) {
				z.leaves[j] = y.leaves[j+t];
				y.leaves[j+t] = null;
			}
		}
		y.nValCnt = t-1;
		for (int j = x.nValCnt +1; j > i + 1; j--) {
			x.leaves[j] = x.leaves[j-1];
		}

		x.leaves[i+1] = z;

		for (int j = x.nValCnt; j > i; j--) {

			x.values[j] = x.values[j-1];
		}
		x.values[i] = y.values[t-1];
		x.nValCnt++;

	}

	public void insert(db_bytes k) {
		db_index_node r = root;
		if (r.nValCnt == 2 * t -1) {
			db_index_node s = new db_index_node();
			root = s;

			s.leaf = false;
			s.nValCnt = 0;
			s.leaves[0] = r;
			split(s, 0, r);
			insertno(s, k, s.values[0]);
		}
		else
			insertno(r, k, null);
	}

	private void insertno(db_index_node x, db_bytes k, db_index_value oPrev) {

		int i = x.nValCnt;

		if (x.leaf) {

			while (i > 0 && compareSets(k, x.values[i-1].oBytes)) {
				x.values[i] = x.values[i-1];	
				i--;
			}
			x.values[i] = new db_index_value(k.getBytes().clone());
			db_index_value oTemp = null;
			
			// Add on to the original algorithm
			// Adds a pointer to each value,
			// that points the the following value
			
			if (i > 0) {
				oTemp = x.values[i-1].oNext;
				x.values[i-1].oNext = x.values[i];
				x.values[i].oNext = oTemp;
			} else if (oPrev != null) {
				oTemp = oPrev.oNext;
				oPrev.oNext = x.values[i];
				x.values[i].oNext = oTemp;
			} else if (x.nValCnt > 1){
				x.values[i].oNext = x.values[i+1];
			}
			
			x.nValCnt++;
		} else {
			while(i > 0 && compareSets(k, x.values[i-1].oBytes))
				i--;
			if (x.leaves[i] == null) {
				x.leaves[i] = new db_index_node();
				x.leaves[i].leaf = true;
				x.leaves[i].nValCnt = 0;
			}
			if ( x.leaves[i].nValCnt == 2 * t - 1 ) {
				split(x, i, x.leaves[i]);
				if (!compareSets(k, x.values[i].oBytes)) {
					i = i + 1;
				}
			}
			db_index_value oPrevious = null;
			if (i > 0)
				oPrevious = x.values[i-1];
			insertno(x.leaves[i], k, oPrevious);
		}
	}
	
	private boolean compareSets(db_bytes k, db_bytes x) {
		k.seek(0);
		x.seek(0);
		for (int i = 0; i < oCompares.size(); i++) {
			if (oCompares.get(i).iOperator == db_util.DB_COMPARE_LT) {
				if (oCompares.get(i).iType == db_util.DB_DATATYPE_INT) {
					int a = k.readInt();
					int b = x.readInt();
					if (a < b)
						return true;
					if (a > b)
						return false;
				}

			} else {
				if (oCompares.get(i).iType == db_util.DB_DATATYPE_INT){
					if (oCompares.get(i).iType == db_util.DB_DATATYPE_INT) {
						int a = k.readInt();
						int b = x.readInt();
						if (a < b)
							return false;
						if (a > b)
							return true;
					}
				}
			}
		}
		return false;

	}
	
	private boolean equalSets(db_bytes k, db_bytes x) {
		return Arrays.equals(k.getBytes(), x.getBytes());
	}
	
	public void list() {
		listno(root, "");
	}
	
	private void listno(db_index_node oNode, String sTab){
		System.out.print(sTab);
		for (int i = 0; i < oNode.nValCnt; i++) {
			if (!oNode.values[i].bDeleted) {
			oNode.values[i].oBytes.seek(0);
			String sOut = "";
			for (int k = 0; k < oCompares.size(); k++)
				sOut += oNode.values[i].oBytes.readInt() + ",";
			if (oNode.values[i].oNext != null) {
				oNode.values[i].oNext.oBytes.seek(0);
				sOut += "(" +  oNode.values[i].oNext.oBytes.readInt() + "," + oNode.values[i].oNext.oBytes.readInt() + ")";
			}	
			else
				sOut += "F";
			
			System.out.print(sOut + "\t");
			}
		}
		System.out.print("\n");
		String sNewTab = sTab + "\t";
		for (int i = 0; i < oNode.leaves.length; i++) {
			if (oNode.leaves[i] != null)
				listno(oNode.leaves[i], sNewTab);
		}
	}
}